With massive semiconductor memories becoming available at low prices, in-memory database technologies have become a focus of attention as fast-processing techniques for big data. One of the in-memory database technologies is used in data mining, where an enormous amount of data resides on a semiconductor memory (in-memory database) to speed up data accesses and, therefore, searches for information of interest. However, moving the information data from a hard disk device to a semiconductor memory alone only offers expectation of 1 to 2 orders of speed improvement.
It is necessary to clarify challenges of current von Neumann-architecture computers before considering an essence of big data usage.
In current computers, CPU's do all information processing regardless of whether of not the CPU's are suited for the processing they have to perform. For CPU's, for example, data items are analogous to playing cards with their faces down, and the CPU's have to turn over each card (access each address) when searching for information. When a CPU performs information processing such as one to sequentially search for specific information on a memory, an amount of information processing becomes extremely large, leading to a long overall waiting time. This is the bus bottleneck, an inevitable problem of the von Neumann-architecture computers.
Parallel processing (distributed processing) by each CPU is an attempt to solve these challenges, but complicates peripheral circuits to overly enlarge the system.
Based on such a background, various techniques (software algorithms) have been devised and utilized in order to reduce the CPU load and the number of information processing procedures for the current computers with the bus bottleneck.
For example, representative algorithms utilized for information search include hash table, index, tree structure, binary search and clustering algorithms and, considering their combinations, the number of possible algorithms is practically infinite. These techniques (software algorithms) are merely means for reducing the CPU load and the number of information processing procedures to thereby take full advantage of the CPUs with the above inherent problem. In other words, any of the above algorithms is a method for, for example, organizing types and in-memory locations of information pieces ahead of time, creating headers and their routes so that a CPU can easily find information, arranging data items according to their sizes.
According to such algorithms, the CPU load is reduced during the search, but pre- and post-processing mandates complex information processing. For example, in data insertion or deletion, data rearrangement or reordering is required every time a data item is added or deleted as the pre- and post-processing for these algorithms.
In order to build an optimal system for a particular database, it is necessary to select some of the software algorithms described above according to a type and/or a scale of the database, and this can be done only by experts with appropriate knowledge and experience.
These and other inherent problems of the current computers arise from the fact that the CPU performs all the information processing, but from a different point of view, if the memory can find specific information by itself, the information processing discussed above will totally change.
Content-addressable memories (CAM) exist as a technology to eliminate the above and other problems. However, content-addressable memories (CAMs) have challenges that they each needs a completely parallel comparison circuit which increases their overall circuit size, and that parallel circuits constituting the comparison circuit consume high current. For this reason, utilization of the content-addressable memories (CAMs) has been limited to special applications where super fast search is essential as in communication routers.
Considering the above situation, the purpose of the present invention is to provide a memory with a new concept to enable a big data search at a speed comparable to that of content-addressable memories (CAM) by simply incorporating an extremely small number of circuits into a common memory.
In order to attain the same objective, the present inventor has been devising various inventions. For example, Japanese Patent No. 4588114, “Memory Provided with Information Refinement Detection Function” by the present inventor discloses a memory with a strong capability of logical product operations such as pattern matching. Also, PCT/JP2013/059260 “Memory Provided with Set Operation Function” discloses a memory capable of expanding the concept of the above memory provided with the information refinement detection function to thereby freely enable logical product operations, logical sum operations and logical negation operations, etc. The disclosures of these two applications are incorporated herein by reference in their entirety.
A memory 101 of the present invention may be applied to the above two prior inventions.
Also, Japanese Patent Application No. 10-232531 “Memory with Operation Function” has an objective, as it illustrates, to improve a chip efficiency by providing an operation circuit for each block unit. This reduces the size of operation circuitry compared to providing an operation circuit for each memory, but deteriorates the operation efficiency as well as having a poor chip efficiency and undesirable cost issues.
Memories with an operation function disclosed in other patent publications are similar to this, and there is no prior invention found for performing parallel information processing on data in a memory with a minimum configuration of one set of operation function as the present invention does.